# 剑指Offer题解 - Day51

# 剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

1
2

限制：

1 <= 数组长度 <= 50000

思路：

如果说，将数组进行排序，那么出现次数超过一半的数字肯定位于数组的中位数。

# 中位数

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let result = nums.sort((a, b) => a - b) // 排序
    return result[Math.floor(nums.length / 2)] // 获取中位数
};

1
2
3
4
5
6
7
8

分析：

本方法是最简单易懂的方法，但是直接使用API来题解不能达到出题者的目的。因此还需要寻找更优解。

# 哈希表

同样的，我们可以用哈希表来存储每个数字出现的次数，然后找出出现次数最多的即可。该方法的时间复杂度和空间复杂度均为O(n) 。

# 摩尔投票法

该方法的原理是票数的正负抵消。从而获取到出现次数超过一半的数字。

首先寻找规律，首先称出现次数超过一半的数字为众数：

如果是众数则投票 +1 ，如果不是众数则投票 -1 ，最后的结果一定 大于0 ；
如果数组的前面部分数字的票数和为 0 ，则剩余数字的票数和一定 大于0，并且众数依旧不变 ****；

根据上述两条规律，可以根据投票数为 0 不断缩小数组的范围，最终剩余的数字就是众数。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let res = 0; // 初始化众数为0
    let votes = 0; // 初始化投票数为0
    for (const num of nums) {
        if (votes === 0) res = num; // 当投票数为0时，假设当前元素就是众数
        votes += num === res ? 1 : -1; // 投票
    }
    return res; // 返回众数
};

1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度 O(n)。
空间复杂度 O(1)。

分析：

核心思路是：当投票数为0时，假设当前元素就是众数。然后根据投票规则进行投票：如果是众数则投票 +1 ，如果不是众数则投票 -1 。

当下次遇到投票数为 0 时，前面所有的元素就可以丢弃了，因为这意味着众数还在剩余元素里面。此时继续假设当前元素为众数，执行投票的逻辑。

直到遍历完数组，最终的结果res就是众数。然后返回res即可。

由于需要遍历整个数组，因此时间复杂度是O(n) ，声明常数级别的变量占用O(1)的空间。

# 总结

本题既可以排序取中位数，又可以通过哈希表统计出现次数。效率最高的办法是第三种：投票法。通过正负抵消的方式，最终留下来的就是众数。

剑指Offer题解 - Day50 剑指Offer题解 - Day52